/**
 * @author: lk
 * @data: 2021/11/11 10:38
 */
package LeetCode;

import selectionSort.ArrayGenerator;

/**
 * 颜色分类。其实就是一次三路快排的一次partition过程
 * 用两种循环不变量进行操作的：
 * 一个是[0,zero]=0, (zero,one)=1, [two, nums.length-1)=2
 * 另一个是[0,zero)=0, [zero,one)=1, (two, nums.length-1)=2
 * 终于是将开区间的循环不变量想对了。
 */
public class _75_215 {
    public static void main(String[] args) {
//        int[] nums = ArrayGenerator.generateIntRandomArray(100, 3);
//        new _75().sortColors2(nums);
//        for (int x : nums) {
//            System.out.printf("%d,", x);
//        }

        int[] nums = ArrayGenerator.generateIntRandomArray(500, 100);
        int res = new _75_215().findKthLargest(nums,1);
        System.out.println(res);
        for (int x : nums) {
            System.out.printf("%d,", x);
        }
    }

    public int findKthLargest(int[] nums, int k) {
        return findkkk(nums,k);
    }

    private int findkkk(int[] nums, int k) {
        return findK(nums, 0, nums.length - 1, k);
    }

    /**
     * 快排。
     * @param nums
     * @param low
     * @param high
     */
    private void sortHelper(int[] nums, int low, int high) {
        if(nums == null || low >= high)
            return;
        int pivot = partition(nums, low, high);
        sortHelper(nums,low,pivot-1);
        sortHelper(nums,pivot+1,high);
    }

    /**
     * 找第k大的元素的题解。
     * @param nums
     * @param low
     * @param high
     * @param k
     * @return
     */
    private int findK(int[] nums, int low, int high,int k) {
        System.out.printf("Now in findK, from[%d,%d] find %d min\n",low,high,k);
//        if(nums == null || low >= high)
//            return -1;
//        if(nums==null )
//            return -1;
//        if(high<=low)
//            return nums[high];
        int pivot = partition(nums, low, high);
        if (pivot ==k )
            return nums[pivot];
        else if(pivot > k)
            return findK(nums, low, pivot - 1, k);
        else
            return findK(nums, pivot+1,high,k);

    }

    /**
     * 自己实现的开区间版三路划分操作。
     * 画图确实很有用。准备好循环不变量后，最好是有图示。
     * @param nums
     * @param low
     * @param high
     * @return
     */
    private int partition(int[] nums, int low, int high) {
        System.out.printf("Now in partition ,[%d, %d]\n",low,high);
        //[low+1,lt)<v, [lt,eq)=v, (gt,high]>v;
        int lt = low + 1, eq = low + 1, gt = high;
        int v = nums[low];
        while (eq <= high) {
            while (eq <= high && nums[eq] == v)
                ++eq;
            while (eq <= high && nums[eq] < v) {
                swap(nums, eq, lt);
                lt++;
                eq++;
            }
            while (eq <= high && nums[eq] > v) {
                swap(nums,eq,high);
                high--;
            }
        }
        swap(nums,high,low);
        return high;
    }

    private void swap(int[] nums, int i, int j) {
        int tmp = nums[i];
        nums[i] = nums[j];
        nums[j] = tmp;
    }

    public void sortColors2(int[] nums) {
        //[0,zero)=0, [zero,one)=1, (two, nums.length-1)=2
        int zero = 0, one = 0, two = nums.length - 1;
        while (one <= two) {
            if (nums[one] == 0) {
                swap(nums, zero, one);
                zero++;
                one++;
            } else if (nums[one] == 1) {
                one++;
            } else {
                swap(nums, one, two);
                two--;
            }
        }

    }

    public void sortColors(int[] nums) {
        //[0,zero]=0, (zero,one)=1, [two, nums.length-1)=2
        int zero = -1, one = 0, two = nums.length;
        while (one < two) {
            if (nums[one] == 0) {
                zero++;
                swap(nums, zero, one);
                one++;
            } else if (nums[one] == 1) {
                one++;
            } else {
                two--;
                swap(nums, one, two);
            }
        }

    }



}
